\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}
\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}

%nonstandard package for chinese letters
%if we don't need chinese letters it can be removed
%\usepackage{CJKutf8}

\renewcommand{\headheight}{16pt}

\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 4}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
 	\HRule\\
%	\HRule\\[2cm]
	
\end{center}

\section{Exercise 4.1: Discussion}
\begin{enumerate}[1.]
 \item
 Global query optimisation can take place at compile time or at runtime. It's also possible to mix this two approaches in example:
   \begin{itemize}
     \item Semi-dynamic optimization - pre-optimizes the query at compile time, but changes it, if it doesn't meet the requirements.
     \item Hierarchical optimization - parts of query are optimized at compile time(join order, join methods, access paths) and other parts are added during execution(possibly locally).
   \end{itemize}
 \item
   Basic techniques to find "good" plans are(mostly heuristics):
   \begin{itemize}
     \item Projections and selections when accessing base relations, joins instead of Cartesian products.
     \item Balancing shape of join trees.
     \item Using dynamic programming to combine the above.
     \item Randomized search.
     \item Trying to predict cost using statistics.
   \end{itemize}
 \item First of all, let's assume all relations are 2-ary. Then the number of possible join trees is equal to number of N inner-vertices binary trees times permutations of N. That is Catalan's number times $N!$ and is $O(2N!)$. If we count only linear trees we get $N! * 2^{(N-1)}$. We usually prefer bushy join trees since they are easier to paralelize, so searching for a good query execution in bushy trees is almost as expensive as in all possible trees. For example: if $N = 3$, there are $3! * 4 = 24$ possible linear join trees and more than $100$ of all join trees.
\end{enumerate}


\section{Exercise 4.2: Selectivity and cardinality}
\begin{enumerate}[a)]
 \item Selectivity - Ratio between expected number of result tuples and tuples of the input relation. Low/high selectivity - we expect small/large amount of result in comparison with a size of the input.\\
Selectivity influences on result size and performance/execution time. (the higher selectivity ratio is, the larger the size of relation is and the longer performance time)

 \item $SF_S( A \in \{ v_1, ..., v_n \}, R) = \frac{n}{values_{A,R}}$


 \item $card(\pi_{A_1, A_2, ..., A_n}(R)) = min\{ card(R), values_{A_1,R} * values_{A_2, R} * ... *  values_{A_n, R} \}$


 \item
  \begin{itemize}
   \item
    \large
    $card(\sigma_{A \geq v}(R)) = \sum_{j = i+1}^{\#buckets}{f_j} + ( \frac{max(range_i) - v }{max(range_i) - min(range_i)} * f_i )$\\
    \normalsize
    where $i$ is the number of bucket, in which $v$ is included
   \item
    \large
    $card(\sigma_{A \geq v}(R)) = \sum_{j = i+1}^{k-1}{f_j} +    ( \frac{v_2 - min(range_k) }{max(range_k) - min(range_k)} * f_k )  ( \frac{max(range_i) - v_1 }{max(range_i) - min(range_i)} * f_i )$\\
    \normalsize
    $i$ is the number of bucket, in which $v_2$ is included,\\
    $k$ is the number of bucket, in which $v_1$ is included
  \end{itemize}
\end{enumerate}

\section{Exercise 4.3: Search space}
\begin{enumerate}[a)]
 \item First we consider the size of relation. Let the size of the search space be $f(n)$,\\
    $f(n)=2^{n-1}*n!$
      We have both left and right-deep trees, 3 types of joins and m replications for each relation.\\
      So the size is $2^{n-1}*n!*3^n*m^n$.

 \item Since each operation can be execute at any one of the k nodes and we have n-1 steps of operation, the size is (a) multiplied $k^{n-1}$, which is $2^{n-1}*n!*3^n*m^n*k^n$.

 \item We can apply pipelining in Hash (single and double). So we have 5 types of joins.\\
 The size is $2^{n-1}*n!*5^n*m^n*k^n$

 \item Suppose $R_1$ is the center of the star, the first join must involve $R_1$, all the other joins is arbitrary.
       $f(n)=2^n*(n-1)!$\\
       The size is $2^n*(n-1)!*3^n*m^n$.

 \item  First, we should pick up one relation $R_1$ in the circle, it has n alternative relations.\\
Second, we should pick up the left or the right one of $R_1$ in the circle, so the result is $2^n*n$ now.\\
Then, each step we only have one choice. So the result remains $2^n*n$.\\
Since each relation has m replications, we should multiply $m^n$ to the result.\\
Considering the execution sites, since each operation can only be done in the newly added node. The result remains $2^n*n*m^n$.
With the 3 type of joins, the final result is $2^n*n*m^n*3^n$.

\end{enumerate}


\end{document}
